GitBucket
Newer
#if !BESTHTTP_DISABLE_ALTERNATE_SSL && (!UNITY_WEBGL || UNITY_EDITOR)
#pragma warning disable
using System;
using BestHTTP.SecureProtocol.Org.BouncyCastle.Utilities;
namespace BestHTTP.SecureProtocol.Org.BouncyCastle.Math.EC.Multiplier
{
public abstract class WNafUtilities
{
public static readonly string PRECOMP_NAME = "bc_wnaf";
private static readonly int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[]{ 13, 41, 121, 337, 897, 2305 };
private static readonly int MAX_WIDTH = 16;
private static readonly ECPoint[] EMPTY_POINTS = new ECPoint[0];
public static void ConfigureBasepoint(ECPoint p)
{
ECCurve c = p.Curve;
if (null == c)
return;
BigInteger n = c.Order;
int bits = (null == n) ? c.FieldSize + 1 : n.BitLength;
int confWidth = System.Math.Min(MAX_WIDTH, GetWindowSize(bits) + 3);
c.Precompute(p, PRECOMP_NAME, new ConfigureBasepointCallback(c, confWidth));
}
public static int[] GenerateCompactNaf(BigInteger k)
{
if ((k.BitLength >> 16) != 0)
throw new ArgumentException("must have bitlength < 2^16", "k");
if (k.SignValue == 0)
return Arrays.EmptyInts;
BigInteger _3k = k.ShiftLeft(1).Add(k);
int bits = _3k.BitLength;
int[] naf = new int[bits >> 1];
BigInteger diff = _3k.Xor(k);
int highBit = bits - 1, length = 0, zeroes = 0;
for (int i = 1; i < highBit; ++i)
{
if (!diff.TestBit(i))
{
++zeroes;
continue;
}
int digit = k.TestBit(i) ? -1 : 1;
naf[length++] = (digit << 16) | zeroes;
zeroes = 1;
++i;
}
naf[length++] = (1 << 16) | zeroes;
if (naf.Length > length)
{
naf = Trim(naf, length);
}
return naf;
}
public static int[] GenerateCompactWindowNaf(int width, BigInteger k)
{
if (width == 2)
{
return GenerateCompactNaf(k);
}
if (width < 2 || width > 16)
throw new ArgumentException("must be in the range [2, 16]", "width");
if ((k.BitLength >> 16) != 0)
throw new ArgumentException("must have bitlength < 2^16", "k");
if (k.SignValue == 0)
return Arrays.EmptyInts;
int[] wnaf = new int[k.BitLength / width + 1];
// 2^width and a mask and sign bit set accordingly
int pow2 = 1 << width;
int mask = pow2 - 1;
int sign = pow2 >> 1;
bool carry = false;
int length = 0, pos = 0;
while (pos <= k.BitLength)
{
if (k.TestBit(pos) == carry)
{
++pos;
continue;
}
k = k.ShiftRight(pos);
int digit = k.IntValue & mask;
if (carry)
{
++digit;
}
carry = (digit & sign) != 0;
if (carry)
{
digit -= pow2;
}
int zeroes = length > 0 ? pos - 1 : pos;
wnaf[length++] = (digit << 16) | zeroes;
pos = width;
}
// Reduce the WNAF array to its actual length
if (wnaf.Length > length)
{
wnaf = Trim(wnaf, length);
}
return wnaf;
}
public static byte[] GenerateJsf(BigInteger g, BigInteger h)
{
int digits = System.Math.Max(g.BitLength, h.BitLength) + 1;
byte[] jsf = new byte[digits];
BigInteger k0 = g, k1 = h;
int j = 0, d0 = 0, d1 = 0;
int offset = 0;
while ((d0 | d1) != 0 || k0.BitLength > offset || k1.BitLength > offset)
{
int n0 = ((int)((uint)k0.IntValue >> offset) + d0) & 7;
int n1 = ((int)((uint)k1.IntValue >> offset) + d1) & 7;
int u0 = n0 & 1;
if (u0 != 0)
{
u0 -= (n0 & 2);
if ((n0 + u0) == 4 && (n1 & 3) == 2)
{
u0 = -u0;
}
}
int u1 = n1 & 1;
if (u1 != 0)
{
u1 -= (n1 & 2);
if ((n1 + u1) == 4 && (n0 & 3) == 2)
{
u1 = -u1;
}
}
if ((d0 << 1) == 1 + u0)
{
d0 ^= 1;
}
if ((d1 << 1) == 1 + u1)
{
d1 ^= 1;
}
if (++offset == 30)
{
offset = 0;
k0 = k0.ShiftRight(30);
k1 = k1.ShiftRight(30);
}
jsf[j++] = (byte)((u0 << 4) | (u1 & 0xF));
}
// Reduce the JSF array to its actual length
if (jsf.Length > j)
{
jsf = Trim(jsf, j);
}
return jsf;
}
public static byte[] GenerateNaf(BigInteger k)
{
if (k.SignValue == 0)
return Arrays.EmptyBytes;
BigInteger _3k = k.ShiftLeft(1).Add(k);
int digits = _3k.BitLength - 1;
byte[] naf = new byte[digits];
BigInteger diff = _3k.Xor(k);
for (int i = 1; i < digits; ++i)
{
if (diff.TestBit(i))
{
naf[i - 1] = (byte)(k.TestBit(i) ? -1 : 1);
++i;
}
}
naf[digits - 1] = 1;
return naf;
}
/**
* Computes the Window NAF (non-adjacent Form) of an integer.
* @param width The width <code>w</code> of the Window NAF. The width is
* defined as the minimal number <code>w</code>, such that for any
* <code>w</code> consecutive digits in the resulting representation, at
* most one is non-zero.
* @param k The integer of which the Window NAF is computed.
* @return The Window NAF of the given width, such that the following holds:
* <code>k = &sum;<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup>
* </code>, where the <code>k<sub>i</sub></code> denote the elements of the
* returned <code>byte[]</code>.
*/
public static byte[] GenerateWindowNaf(int width, BigInteger k)
{
if (width == 2)
{
return GenerateNaf(k);
}
if (width < 2 || width > 8)
throw new ArgumentException("must be in the range [2, 8]", "width");
if (k.SignValue == 0)
return Arrays.EmptyBytes;
byte[] wnaf = new byte[k.BitLength + 1];
// 2^width and a mask and sign bit set accordingly
int pow2 = 1 << width;
int mask = pow2 - 1;
int sign = pow2 >> 1;
bool carry = false;
int length = 0, pos = 0;
while (pos <= k.BitLength)
{
if (k.TestBit(pos) == carry)
{
++pos;
continue;
}
k = k.ShiftRight(pos);
int digit = k.IntValue & mask;
if (carry)
{
++digit;
}
carry = (digit & sign) != 0;
if (carry)
{
digit -= pow2;
}
length += (length > 0) ? pos - 1 : pos;
wnaf[length++] = (byte)digit;
pos = width;
}
// Reduce the WNAF array to its actual length
if (wnaf.Length > length)
{
wnaf = Trim(wnaf, length);
}
return wnaf;
}
public static int GetNafWeight(BigInteger k)
{
if (k.SignValue == 0)
return 0;
BigInteger _3k = k.ShiftLeft(1).Add(k);
BigInteger diff = _3k.Xor(k);
return diff.BitCount;
}
public static WNafPreCompInfo GetWNafPreCompInfo(ECPoint p)
{
return GetWNafPreCompInfo(p.Curve.GetPreCompInfo(p, PRECOMP_NAME));
}
public static WNafPreCompInfo GetWNafPreCompInfo(PreCompInfo preCompInfo)
{
return preCompInfo as WNafPreCompInfo;
}
/**
* Determine window width to use for a scalar multiplication of the given size.
*
* @param bits the bit-length of the scalar to multiply by
* @return the window size to use
*/
public static int GetWindowSize(int bits)
{
return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS, MAX_WIDTH);
}
/**
* Determine window width to use for a scalar multiplication of the given size.
*
* @param bits the bit-length of the scalar to multiply by
* @param maxWidth the maximum window width to return
* @return the window size to use
*/
public static int GetWindowSize(int bits, int maxWidth)
{
return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS, maxWidth);
}
/**
* Determine window width to use for a scalar multiplication of the given size.
*
* @param bits the bit-length of the scalar to multiply by
* @param windowSizeCutoffs a monotonically increasing list of bit sizes at which to increment the window width
* @return the window size to use
*/
public static int GetWindowSize(int bits, int[] windowSizeCutoffs)
{
return GetWindowSize(bits, windowSizeCutoffs, MAX_WIDTH);
}
/**
* Determine window width to use for a scalar multiplication of the given size.
*
* @param bits the bit-length of the scalar to multiply by
* @param windowSizeCutoffs a monotonically increasing list of bit sizes at which to increment the window width
* @param maxWidth the maximum window width to return
* @return the window size to use
*/
public static int GetWindowSize(int bits, int[] windowSizeCutoffs, int maxWidth)
{
int w = 0;
for (; w < windowSizeCutoffs.Length; ++w)
{
if (bits < windowSizeCutoffs[w])
{
break;
}
}
return System.Math.Max(2, System.Math.Min(maxWidth, w + 2));
}
[Obsolete]
public static ECPoint MapPointWithPrecomp(ECPoint p, int minWidth, bool includeNegated,
ECPointMap pointMap)
{
ECCurve c = p.Curve;
WNafPreCompInfo infoP = Precompute(p, minWidth, includeNegated);
ECPoint q = pointMap.Map(p);
c.Precompute(q, PRECOMP_NAME, new MapPointCallback(infoP, includeNegated, pointMap));
return q;
}
public static WNafPreCompInfo Precompute(ECPoint p, int minWidth, bool includeNegated)
{
return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME,
new PrecomputeCallback(p, minWidth, includeNegated));
}
public static WNafPreCompInfo PrecomputeWithPointMap(ECPoint p, ECPointMap pointMap, WNafPreCompInfo fromWNaf,
bool includeNegated)
{
return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME,
new PrecomputeWithPointMapCallback(p, pointMap, fromWNaf, includeNegated));
}
private static byte[] Trim(byte[] a, int length)
{
byte[] result = new byte[length];
Array.Copy(a, 0, result, 0, result.Length);
return result;
}
private static int[] Trim(int[] a, int length)
{
int[] result = new int[length];
Array.Copy(a, 0, result, 0, result.Length);
return result;
}
private static ECPoint[] ResizeTable(ECPoint[] a, int length)
{
ECPoint[] result = new ECPoint[length];
Array.Copy(a, 0, result, 0, a.Length);
return result;
}
private class ConfigureBasepointCallback
: IPreCompCallback
{
private readonly ECCurve m_curve;
private readonly int m_confWidth;
internal ConfigureBasepointCallback(ECCurve curve, int confWidth)
{
this.m_curve = curve;
this.m_confWidth = confWidth;
}
public PreCompInfo Precompute(PreCompInfo existing)
{
WNafPreCompInfo existingWNaf = existing as WNafPreCompInfo;
if (null != existingWNaf && existingWNaf.ConfWidth == m_confWidth)
{
existingWNaf.PromotionCountdown = 0;
return existingWNaf;
}
WNafPreCompInfo result = new WNafPreCompInfo();
result.PromotionCountdown = 0;
result.ConfWidth = m_confWidth;
if (null != existingWNaf)
{
result.PreComp = existingWNaf.PreComp;
result.PreCompNeg = existingWNaf.PreCompNeg;
result.Twice = existingWNaf.Twice;
result.Width = existingWNaf.Width;
}
return result;
}
}
private class MapPointCallback
: IPreCompCallback
{
private readonly WNafPreCompInfo m_infoP;
private readonly bool m_includeNegated;
private readonly ECPointMap m_pointMap;
internal MapPointCallback(WNafPreCompInfo infoP, bool includeNegated, ECPointMap pointMap)
{
this.m_infoP = infoP;
this.m_includeNegated = includeNegated;
this.m_pointMap = pointMap;
}
public PreCompInfo Precompute(PreCompInfo existing)
{
WNafPreCompInfo result = new WNafPreCompInfo();
result.ConfWidth = m_infoP.ConfWidth;
ECPoint twiceP = m_infoP.Twice;
if (null != twiceP)
{
ECPoint twiceQ = m_pointMap.Map(twiceP);
result.Twice = twiceQ;
}
ECPoint[] preCompP = m_infoP.PreComp;
ECPoint[] preCompQ = new ECPoint[preCompP.Length];
for (int i = 0; i < preCompP.Length; ++i)
{
preCompQ[i] = m_pointMap.Map(preCompP[i]);
}
result.PreComp = preCompQ;
result.Width = m_infoP.Width;
if (m_includeNegated)
{
ECPoint[] preCompNegQ = new ECPoint[preCompQ.Length];
for (int i = 0; i < preCompNegQ.Length; ++i)
{
preCompNegQ[i] = preCompQ[i].Negate();
}
result.PreCompNeg = preCompNegQ;
}
return result;
}
}
private class PrecomputeCallback
: IPreCompCallback
{
private readonly ECPoint m_p;
private readonly int m_minWidth;
private readonly bool m_includeNegated;
internal PrecomputeCallback(ECPoint p, int minWidth, bool includeNegated)
{
this.m_p = p;
this.m_minWidth = minWidth;
this.m_includeNegated = includeNegated;
}
public PreCompInfo Precompute(PreCompInfo existing)
{
WNafPreCompInfo existingWNaf = existing as WNafPreCompInfo;
int width = System.Math.Max(2, System.Math.Min(MAX_WIDTH, m_minWidth));
int reqPreCompLen = 1 << (width - 2);
if (CheckExisting(existingWNaf, width, reqPreCompLen, m_includeNegated))
{
existingWNaf.DecrementPromotionCountdown();
return existingWNaf;
}
WNafPreCompInfo result = new WNafPreCompInfo();
ECCurve c = m_p.Curve;
ECPoint[] preComp = null, preCompNeg = null;
ECPoint twiceP = null;
if (null != existingWNaf)
{
int promotionCountdown = existingWNaf.DecrementPromotionCountdown();
result.PromotionCountdown = promotionCountdown;
int confWidth = existingWNaf.ConfWidth;
result.ConfWidth = confWidth;
preComp = existingWNaf.PreComp;
preCompNeg = existingWNaf.PreCompNeg;
twiceP = existingWNaf.Twice;
}
width = System.Math.Min(MAX_WIDTH, System.Math.Max(result.ConfWidth, width));
reqPreCompLen = 1 << (width - 2);
int iniPreCompLen = 0;
if (null == preComp)
{
preComp = EMPTY_POINTS;
}
else
{
iniPreCompLen = preComp.Length;
}
if (iniPreCompLen < reqPreCompLen)
{
preComp = WNafUtilities.ResizeTable(preComp, reqPreCompLen);
if (reqPreCompLen == 1)
{
preComp[0] = m_p.Normalize();
}
else
{
int curPreCompLen = iniPreCompLen;
if (curPreCompLen == 0)
{
preComp[0] = m_p;
curPreCompLen = 1;
}
ECFieldElement iso = null;
if (reqPreCompLen == 2)
{
preComp[1] = m_p.ThreeTimes();
}
else
{
ECPoint isoTwiceP = twiceP, last = preComp[curPreCompLen - 1];
if (null == isoTwiceP)
{
isoTwiceP = preComp[0].Twice();
twiceP = isoTwiceP;
/*
* For Fp curves with Jacobian projective coordinates, use a (quasi-)isomorphism
* where 'twiceP' is "affine", so that the subsequent additions are cheaper. This
* also requires scaling the initial point's X, Y coordinates, and reversing the
* isomorphism as part of the subsequent normalization.
*
* NOTE: The correctness of this optimization depends on:
* 1) additions do not use the curve's A, B coefficients.
* 2) no special cases (i.e. Q +/- Q) when calculating 1P, 3P, 5P, ...
*/
if (!twiceP.IsInfinity && ECAlgorithms.IsFpCurve(c) && c.FieldSize >= 64)
{
switch (c.CoordinateSystem)
{
case ECCurve.COORD_JACOBIAN:
case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
case ECCurve.COORD_JACOBIAN_MODIFIED:
{
iso = twiceP.GetZCoord(0);
isoTwiceP = c.CreatePoint(twiceP.XCoord.ToBigInteger(),
twiceP.YCoord.ToBigInteger());
ECFieldElement iso2 = iso.Square(), iso3 = iso2.Multiply(iso);
last = last.ScaleX(iso2).ScaleY(iso3);
if (iniPreCompLen == 0)
{
preComp[0] = last;
}
break;
}
}
}
}
while (curPreCompLen < reqPreCompLen)
{
/*
* Compute the new ECPoints for the precomputation array. The values 1, 3,
* 5, ..., 2^(width-1)-1 times p are computed
*/
preComp[curPreCompLen++] = last = last.Add(isoTwiceP);
}
}
/*
* Having oft-used operands in affine form makes operations faster.
*/
c.NormalizeAll(preComp, iniPreCompLen, reqPreCompLen - iniPreCompLen, iso);
}
}
if (m_includeNegated)
{
int pos;
if (null == preCompNeg)
{
pos = 0;
preCompNeg = new ECPoint[reqPreCompLen];
}
else
{
pos = preCompNeg.Length;
if (pos < reqPreCompLen)
{
preCompNeg = WNafUtilities.ResizeTable(preCompNeg, reqPreCompLen);
}
}
while (pos < reqPreCompLen)
{
preCompNeg[pos] = preComp[pos].Negate();
++pos;
}
}
result.PreComp = preComp;
result.PreCompNeg = preCompNeg;
result.Twice = twiceP;
result.Width = width;
return result;
}
private bool CheckExisting(WNafPreCompInfo existingWNaf, int width, int reqPreCompLen, bool includeNegated)
{
return null != existingWNaf
&& existingWNaf.Width >= System.Math.Max(existingWNaf.ConfWidth, width)
&& CheckTable(existingWNaf.PreComp, reqPreCompLen)
&& (!includeNegated || CheckTable(existingWNaf.PreCompNeg, reqPreCompLen));
}
private bool CheckTable(ECPoint[] table, int reqLen)
{
return null != table && table.Length >= reqLen;
}
}
private class PrecomputeWithPointMapCallback
: IPreCompCallback
{
private readonly ECPoint m_point;
private readonly ECPointMap m_pointMap;
private readonly WNafPreCompInfo m_fromWNaf;
private readonly bool m_includeNegated;
internal PrecomputeWithPointMapCallback(ECPoint point, ECPointMap pointMap, WNafPreCompInfo fromWNaf,
bool includeNegated)
{
this.m_point = point;
this.m_pointMap = pointMap;
this.m_fromWNaf = fromWNaf;
this.m_includeNegated = includeNegated;
}
public PreCompInfo Precompute(PreCompInfo existing)
{
WNafPreCompInfo existingWNaf = existing as WNafPreCompInfo;
int width = m_fromWNaf.Width;
int reqPreCompLen = m_fromWNaf.PreComp.Length;
if (CheckExisting(existingWNaf, width, reqPreCompLen, m_includeNegated))
{
existingWNaf.DecrementPromotionCountdown();
return existingWNaf;
}
/*
* TODO Ideally this method would support incremental calculation, but given the
* existing use-cases it would be of little-to-no benefit.
*/
WNafPreCompInfo result = new WNafPreCompInfo();
result.PromotionCountdown = m_fromWNaf.PromotionCountdown;
ECPoint twiceFrom = m_fromWNaf.Twice;
if (null != twiceFrom)
{
ECPoint twice = m_pointMap.Map(twiceFrom);
result.Twice = twice;
}
ECPoint[] preCompFrom = m_fromWNaf.PreComp;
ECPoint[] preComp = new ECPoint[preCompFrom.Length];
for (int i = 0; i < preCompFrom.Length; ++i)
{
preComp[i] = m_pointMap.Map(preCompFrom[i]);
}
result.PreComp = preComp;
result.Width = width;
if (m_includeNegated)
{
ECPoint[] preCompNeg = new ECPoint[preComp.Length];
for (int i = 0; i < preCompNeg.Length; ++i)
{
preCompNeg[i] = preComp[i].Negate();
}
result.PreCompNeg = preCompNeg;
}
return result;
}
private bool CheckExisting(WNafPreCompInfo existingWNaf, int width, int reqPreCompLen, bool includeNegated)
{
return null != existingWNaf
&& existingWNaf.Width >= width
&& CheckTable(existingWNaf.PreComp, reqPreCompLen)
&& (!includeNegated || CheckTable(existingWNaf.PreCompNeg, reqPreCompLen));
}
private bool CheckTable(ECPoint[] table, int reqLen)
{
return null != table && table.Length >= reqLen;
}
}
}
}
#pragma warning restore
#endif